<html><head><meta charset="utf-8"><title>16 ConcurrentHashMap 源码解析和设计思路-慕课专栏</title>
			<meta http-equiv="X-UA-Compatible" content="IE=edge, chrome=1">
			<meta name="renderer" content="webkit">
			<meta property="qc:admins" content="77103107776157736375">
			<meta property="wb:webmaster" content="c4f857219bfae3cb">
			<meta http-equiv="Access-Control-Allow-Origin" content="*">
			<meta http-equiv="Cache-Control" content="no-transform ">
			<meta http-equiv="Cache-Control" content="no-siteapp">
			<link rel="apple-touch-icon" sizes="76x76" href="https://www.imooc.com/static/img/common/touch-icon-ipad.png">
			<link rel="apple-touch-icon" sizes="120x120" href="https://www.imooc.com/static/img/common/touch-icon-iphone-retina.png">
			<link rel="apple-touch-icon" sizes="152x152" href="https://www.imooc.com/static/img/common/touch-icon-ipad-retina.png">
			<link href="https://moco.imooc.com/captcha/style/captcha.min.css" rel="stylesheet">
			<link rel="stylesheet" href="https://www.imooc.com/static/moco/v1.0/dist/css/moco.min.css?t=201907021539" type="text/css">
			<link rel="stylesheet" href="https://www.imooc.com/static/lib/swiper/swiper-3.4.2.min.css?t=201907021539">
			<link rel="stylesheet" href="https://static.mukewang.com/static/css/??base.css,common/common-less.css?t=2.5,column/zhuanlanChapter-less.css?t=2.5,course/inc/course_tipoff-less.css?t=2.5?v=201907051055" type="text/css">
			<link charset="utf-8" rel="stylesheet" href="https://www.imooc.com/static/lib/ueditor/themes/imooc/css/ueditor.css?v=201907021539"><link rel="stylesheet" href="https://www.imooc.com/static/lib/baiduShare/api/css/share_style0_16.css?v=6aba13f0.css"></head>
			<body><div id="main">


<div class="main-con hide-menu">
    <!-- 左侧菜单 & 索引 -->
    
    <div class="right-content" style="padding-left: 0px;">
        <div class="container clearfix" id="top" style="width: 1134px; display: block;">
            
            
            <div class="center_con js-center_con l" style="width: 1134px;">
                <div class="article-con">
                                            <!-- 买过的阅读 -->
                        

                    
                    <div class="art-title" style="margin-top: 0px;">
                        16 ConcurrentHashMap 源码解析和设计思路
                    </div>
                    <div class="art-info clearfix">
                        
                        <span class="l">
                            更新时间：2019-10-01 20:53:45
                        </span>
                    </div>
                    <div class="art-top">
                                                <img src="https://img4.mukewang.com/5d89764e0001be1e06400359.jpg" alt="">
                                                                        <div class="famous-word-box">
                            <img src="https://www.imooc.com/static/img/column/bg-l.png" alt="" class="bg1 bg">
                            <img src="https://www.imooc.com/static/img/column/bg-r.png" alt="" class="bg2 bg">
                            <div class="famous-word">与有肝胆人共事，从无字句处读书。<p class="author">——周恩来</p></div>
                        </div>
                                            </div>
                    <div class="art-content js-lookimg">
                        <div id="article_content">
                            <div class="cl-preview-section"><h2 id="引导语" style="font-size: 30px;">引导语</h2>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">当我们碰到线程不安全场景下，需要使用 Map 的时候，我们第一个想到的 API 估计就是 ConcurrentHashMap，ConcurrentHashMap 内部封装了锁和各种数据结构来保证访问 Map 是线程安全的，接下来我们一一来看下，和 HashMap 相比，多了哪些数据结构，又是如何保证线程安全的。</p>
</div><div class="cl-preview-section"><h2 id="类注释" style="font-size: 30px;">1 类注释</h2>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">我们从类注释上大概可以得到如下信息：</p>
</div><div class="cl-preview-section"><ol>
<li style="font-size: 20px; line-height: 38px;">所有的操作都是线程安全的，我们在使用时，无需再加锁；</li>
<li style="font-size: 20px; line-height: 38px;">多个线程同时进行 put、remove 等操作时并不会阻塞，可以同时进行，和 HashTable 不同，HashTable 在操作时，会锁住整个 Map；</li>
<li style="font-size: 20px; line-height: 38px;">迭代过程中，即使 Map 结构被修改，也不会抛 ConcurrentModificationException 异常；</li>
<li style="font-size: 20px; line-height: 38px;">除了数组 + 链表 + 红黑树的基本结构外，新增了转移节点，是为了保证扩容时的线程安全的节点；</li>
<li style="font-size: 20px; line-height: 38px;">提供了很多 Stream 流式方法，比如说：forEach、search、reduce 等等。</li>
</ol>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">从类注释中，我们可以看出 ConcurrentHashMap 和 HashMap 相比，新增了转移节点的数据结构，至于底层如何实现线程安全，转移节点的具体细节，暂且看不出来，接下来我们细看源码。</p>
</div><div class="cl-preview-section"><h2 id="结构" style="font-size: 30px;">2 结构</h2>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">虽然 ConcurrentHashMap 的底层数据结构，和方法的实现细节和 HashMap 大体一致，但两者在类结构上却没有任何关联，我们看下 ConcurrentHashMap 的类图：<br>
<img class="" src="https://img.mukewang.com/5d883afd0001a01a04670199.png" data-original="//img.mukewang.com/5d883afd0001a01a04670199.png" alt="图片描述"><br>
看 ConcurrentHashMap 源码，我们会发现很多方法和代码和 HashMap 很相似，有的同学可能会问，为什么不继承 HashMap 呢？继承的确是个好办法，但尴尬的是，ConcurrentHashMap 都是在方法中间进行一些加锁操作，也就是说加锁把方法切割了，继承就很难解决这个问题。</p>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">ConcurrentHashMap 和 HashMap 两者的相同之处：</p>
</div><div class="cl-preview-section"><ol>
<li style="font-size: 20px; line-height: 38px;">数组、链表结构几乎相同，所以底层对数据结构的操作思路是相同的（只是思路相同，底层实现不同）；</li>
<li style="font-size: 20px; line-height: 38px;">都实现了 Map 接口，继承了 AbstractMap 抽象类，所以大多数的方法也都是相同的，HashMap 有的方法，ConcurrentHashMap 几乎都有，所以当我们需要从 HashMap 切换到 ConcurrentHashMap 时，无需关心两者之间的兼容问题。</li>
</ol>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">不同之处：</p>
</div><div class="cl-preview-section"><ol>
<li style="font-size: 20px; line-height: 38px;">红黑树结构略有不同，HashMap 的红黑树中的节点叫做 TreeNode，TreeNode 不仅仅有属性，还维护着红黑树的结构，比如说查找，新增等等；ConcurrentHashMap 中红黑树被拆分成两块，TreeNode 仅仅维护的属性和查找功能，新增了 TreeBin，来维护红黑树结构，并负责根节点的加锁和解锁；</li>
<li style="font-size: 20px; line-height: 38px;">新增 ForwardingNode （转移）节点，扩容的时候会使用到，通过使用该节点，来保证扩容时的线程安全。</li>
</ol>
</div><div class="cl-preview-section"><h2 id="put" style="font-size: 30px;">3 put</h2>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">ConcurrentHashMap 在 put 方法上的整体思路和 HashMap 相同，但在线程安全方面写了很多保障的代码，我们先来看下大体思路：</p>
</div><div class="cl-preview-section"><ol>
<li style="font-size: 20px; line-height: 38px;">如果数组为空，初始化，初始化完成之后，走 2；</li>
<li style="font-size: 20px; line-height: 38px;">计算当前槽点有没有值，没有值的话，cas 创建，失败继续自旋（for 死循环），直到成功，槽点有值的话，走 3；</li>
<li style="font-size: 20px; line-height: 38px;">如果槽点是转移节点(正在扩容)，就会一直自旋等待扩容完成之后再新增，不是转移节点走 4；</li>
<li style="font-size: 20px; line-height: 38px;">槽点有值的，先锁定当前槽点，保证其余线程不能操作，如果是链表，新增值到链表的尾部，如果是红黑树，使用红黑树新增的方法新增；</li>
<li style="font-size: 20px; line-height: 38px;">新增完成之后 check 需不需要扩容，需要的话去扩容。</li>
</ol>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">具体源码如下：</p>
</div><div class="cl-preview-section"><pre class="  language-java"><code class="prism  language-java"><span class="token keyword">final</span> V <span class="token function">putVal</span><span class="token punctuation">(</span>K key<span class="token punctuation">,</span> V value<span class="token punctuation">,</span> <span class="token keyword">boolean</span> onlyIfAbsent<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>key <span class="token operator">==</span> null <span class="token operator">||</span> value <span class="token operator">==</span> null<span class="token punctuation">)</span> <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">NullPointerException</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment">//计算hash</span>
    <span class="token keyword">int</span> hash <span class="token operator">=</span> <span class="token function">spread</span><span class="token punctuation">(</span>key<span class="token punctuation">.</span><span class="token function">hashCode</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> binCount <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span>Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span><span class="token punctuation">[</span><span class="token punctuation">]</span> tab <span class="token operator">=</span> table<span class="token punctuation">;</span><span class="token punctuation">;</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> f<span class="token punctuation">;</span> <span class="token keyword">int</span> n<span class="token punctuation">,</span> i<span class="token punctuation">,</span> fh<span class="token punctuation">;</span>
        <span class="token comment">//table是空的，进行初始化</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>tab <span class="token operator">==</span> null <span class="token operator">||</span> <span class="token punctuation">(</span>n <span class="token operator">=</span> tab<span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span>
            tab <span class="token operator">=</span> <span class="token function">initTable</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment">//如果当前索引位置没有值，直接创建</span>
        <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>f <span class="token operator">=</span> <span class="token function">tabAt</span><span class="token punctuation">(</span>tab<span class="token punctuation">,</span> i <span class="token operator">=</span> <span class="token punctuation">(</span>n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">&amp;</span> hash<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">==</span> null<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token comment">//cas 在 i 位置创建新的元素，当 i 位置是空时，即能创建成功，结束for自循，否则继续自旋</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">casTabAt</span><span class="token punctuation">(</span>tab<span class="token punctuation">,</span> i<span class="token punctuation">,</span> null<span class="token punctuation">,</span>
                         <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span><span class="token punctuation">(</span>hash<span class="token punctuation">,</span> key<span class="token punctuation">,</span> value<span class="token punctuation">,</span> null<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>                   <span class="token comment">// no lock when adding to empty bin</span>
        <span class="token punctuation">}</span>
        <span class="token comment">//如果当前槽点是转移节点，表示该槽点正在扩容，就会一直等待扩容完成</span>
        <span class="token comment">//转移节点的 hash 值是固定的，都是 MOVED</span>
        <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>fh <span class="token operator">=</span> f<span class="token punctuation">.</span>hash<span class="token punctuation">)</span> <span class="token operator">==</span> MOVED<span class="token punctuation">)</span>
            tab <span class="token operator">=</span> <span class="token function">helpTransfer</span><span class="token punctuation">(</span>tab<span class="token punctuation">,</span> f<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment">//槽点上有值的</span>
        <span class="token keyword">else</span> <span class="token punctuation">{</span>
            V oldVal <span class="token operator">=</span> null<span class="token punctuation">;</span>
            <span class="token comment">//锁定当前槽点，其余线程不能操作，保证了安全</span>
            <span class="token keyword">synchronized</span> <span class="token punctuation">(</span>f<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                <span class="token comment">//这里再次判断 i 索引位置的数据没有被修改</span>
                <span class="token comment">//binCount 被赋值的话，说明走到了修改表的过程里面</span>
                <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">tabAt</span><span class="token punctuation">(</span>tab<span class="token punctuation">,</span> i<span class="token punctuation">)</span> <span class="token operator">==</span> f<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                    <span class="token comment">//链表</span>
                    <span class="token keyword">if</span> <span class="token punctuation">(</span>fh <span class="token operator">&gt;=</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                        binCount <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
                        <span class="token keyword">for</span> <span class="token punctuation">(</span>Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> e <span class="token operator">=</span> f<span class="token punctuation">;</span><span class="token punctuation">;</span> <span class="token operator">++</span>binCount<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                            K ek<span class="token punctuation">;</span>
                            <span class="token comment">//值有的话，直接返回</span>
                            <span class="token keyword">if</span> <span class="token punctuation">(</span>e<span class="token punctuation">.</span>hash <span class="token operator">==</span> hash <span class="token operator">&amp;&amp;</span>
                                <span class="token punctuation">(</span><span class="token punctuation">(</span>ek <span class="token operator">=</span> e<span class="token punctuation">.</span>key<span class="token punctuation">)</span> <span class="token operator">==</span> key <span class="token operator">||</span>
                                 <span class="token punctuation">(</span>ek <span class="token operator">!=</span> null <span class="token operator">&amp;&amp;</span> key<span class="token punctuation">.</span><span class="token function">equals</span><span class="token punctuation">(</span>ek<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                                oldVal <span class="token operator">=</span> e<span class="token punctuation">.</span>val<span class="token punctuation">;</span>
                                <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>onlyIfAbsent<span class="token punctuation">)</span>
                                    e<span class="token punctuation">.</span>val <span class="token operator">=</span> value<span class="token punctuation">;</span>
                                <span class="token keyword">break</span><span class="token punctuation">;</span>
                            <span class="token punctuation">}</span>
                            Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> pred <span class="token operator">=</span> e<span class="token punctuation">;</span>
                            <span class="token comment">//把新增的元素赋值到链表的最后，退出自旋</span>
                            <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>e <span class="token operator">=</span> e<span class="token punctuation">.</span>next<span class="token punctuation">)</span> <span class="token operator">==</span> null<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                                pred<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span><span class="token punctuation">(</span>hash<span class="token punctuation">,</span> key<span class="token punctuation">,</span>
                                                          value<span class="token punctuation">,</span> null<span class="token punctuation">)</span><span class="token punctuation">;</span>
                                <span class="token keyword">break</span><span class="token punctuation">;</span>
                            <span class="token punctuation">}</span>
                        <span class="token punctuation">}</span>
                    <span class="token punctuation">}</span>
                    <span class="token comment">//红黑树，这里没有使用 TreeNode,使用的是 TreeBin，TreeNode 只是红黑树的一个节点</span>
                    <span class="token comment">//TreeBin 持有红黑树的引用，并且会对其加锁，保证其操作的线程安全</span>
                    <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>f <span class="token keyword">instanceof</span> <span class="token class-name">TreeBin</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                        Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> p<span class="token punctuation">;</span>
                        binCount <span class="token operator">=</span> <span class="token number">2</span><span class="token punctuation">;</span>
                        <span class="token comment">//满足if的话，把老的值给oldVal</span>
                        <span class="token comment">//在putTreeVal方法里面，在给红黑树重新着色旋转的时候</span>
                        <span class="token comment">//会锁住红黑树的根节点</span>
                        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>p <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>TreeBin<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span><span class="token punctuation">)</span>f<span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">putTreeVal</span><span class="token punctuation">(</span>hash<span class="token punctuation">,</span> key<span class="token punctuation">,</span>
                                                       value<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">!=</span> null<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                            oldVal <span class="token operator">=</span> p<span class="token punctuation">.</span>val<span class="token punctuation">;</span>
                            <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>onlyIfAbsent<span class="token punctuation">)</span>
                                p<span class="token punctuation">.</span>val <span class="token operator">=</span> value<span class="token punctuation">;</span>
                        <span class="token punctuation">}</span>
                    <span class="token punctuation">}</span>
                <span class="token punctuation">}</span>
            <span class="token punctuation">}</span>
            <span class="token comment">//binCount不为空，并且 oldVal 有值的情况，说明已经新增成功了</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>binCount <span class="token operator">!=</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                <span class="token comment">// 链表是否需要转化成红黑树</span>
                <span class="token keyword">if</span> <span class="token punctuation">(</span>binCount <span class="token operator">&gt;=</span> TREEIFY_THRESHOLD<span class="token punctuation">)</span>
                    <span class="token function">treeifyBin</span><span class="token punctuation">(</span>tab<span class="token punctuation">,</span> i<span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token keyword">if</span> <span class="token punctuation">(</span>oldVal <span class="token operator">!=</span> null<span class="token punctuation">)</span>
                    <span class="token keyword">return</span> oldVal<span class="token punctuation">;</span>
                <span class="token comment">//这一步几乎走不到。槽点已经上锁，只有在红黑树或者链表新增失败的时候</span>
                <span class="token comment">//才会走到这里，这两者新增都是自旋的，几乎不会失败</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token comment">//check 容器是否需要扩容，如果需要去扩容，调用 transfer 方法去扩容</span>
    <span class="token comment">//如果已经在扩容中了，check有无完成</span>
    <span class="token function">addCount</span><span class="token punctuation">(</span>1L<span class="token punctuation">,</span> binCount<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> null<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">源码中都有非常详细的注释，就不解释了，我们重点说一下，ConcurrentHashMap 在 put 过程中，采用了哪些手段来保证线程安全。</p>
</div><div class="cl-preview-section"><h3 id="数组初始化时的线程安全">3.1 数组初始化时的线程安全</h3>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">数组初始化时，首先通过自旋来保证一定可以初始化成功，然后通过 CAS 设置 SIZECTL 变量的值，来保证同一时刻只能有一个线程对数组进行初始化，CAS 成功之后，还会再次判断当前数组是否已经初始化完成，如果已经初始化完成，就不会再次初始化，通过自旋 + CAS +  双重 check 等手段保证了数组初始化时的线程安全，源码如下：</p>
</div><div class="cl-preview-section"><pre class="  language-java"><code class="prism  language-java"><span class="token comment">//初始化 table，通过对 sizeCtl 的变量赋值来保证数组只能被初始化一次</span>
<span class="token keyword">private</span> <span class="token keyword">final</span> Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span><span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token function">initTable</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span><span class="token punctuation">[</span><span class="token punctuation">]</span> tab<span class="token punctuation">;</span> <span class="token keyword">int</span> sc<span class="token punctuation">;</span>
    <span class="token comment">//通过自旋保证初始化成功</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>tab <span class="token operator">=</span> table<span class="token punctuation">)</span> <span class="token operator">==</span> null <span class="token operator">||</span> tab<span class="token punctuation">.</span>length <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 小于 0 代表有线程正在初始化，释放当前 CPU 的调度权，重新发起锁的竞争</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>sc <span class="token operator">=</span> sizeCtl<span class="token punctuation">)</span> <span class="token operator">&lt;</span> <span class="token number">0</span><span class="token punctuation">)</span>
            Thread<span class="token punctuation">.</span><span class="token function">yield</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// lost initialization race; just spin</span>
        <span class="token comment">// CAS 赋值保证当前只有一个线程在初始化，-1 代表当前只有一个线程能初始化</span>
        <span class="token comment">// 保证了数组的初始化的安全性</span>
        <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>U<span class="token punctuation">.</span><span class="token function">compareAndSwapInt</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">,</span> SIZECTL<span class="token punctuation">,</span> sc<span class="token punctuation">,</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">try</span> <span class="token punctuation">{</span>
                <span class="token comment">// 很有可能执行到这里的时候，table 已经不为空了，这里是双重 check</span>
                <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>tab <span class="token operator">=</span> table<span class="token punctuation">)</span> <span class="token operator">==</span> null <span class="token operator">||</span> tab<span class="token punctuation">.</span>length <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                    <span class="token comment">// 进行初始化</span>
                    <span class="token keyword">int</span> n <span class="token operator">=</span> <span class="token punctuation">(</span>sc <span class="token operator">&gt;</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token operator">?</span> sc <span class="token operator">:</span> DEFAULT_CAPACITY<span class="token punctuation">;</span>
                    <span class="token annotation punctuation">@SuppressWarnings</span><span class="token punctuation">(</span><span class="token string">"unchecked"</span><span class="token punctuation">)</span>
                    Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span><span class="token punctuation">[</span><span class="token punctuation">]</span> nt <span class="token operator">=</span> <span class="token punctuation">(</span>Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token operator">&lt;</span><span class="token operator">?</span><span class="token punctuation">,</span><span class="token operator">?</span><span class="token operator">&gt;</span><span class="token punctuation">[</span>n<span class="token punctuation">]</span><span class="token punctuation">;</span>
                    table <span class="token operator">=</span> tab <span class="token operator">=</span> nt<span class="token punctuation">;</span>
                    sc <span class="token operator">=</span> n <span class="token operator">-</span> <span class="token punctuation">(</span>n <span class="token operator">&gt;&gt;&gt;</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token punctuation">}</span>
            <span class="token punctuation">}</span> <span class="token keyword">finally</span> <span class="token punctuation">{</span>
                sizeCtl <span class="token operator">=</span> sc<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            <span class="token keyword">break</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> tab<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre>
</div><div class="cl-preview-section"><h3 id="新增槽点值时的线程安全">3.2 新增槽点值时的线程安全</h3>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">此时为了保证线程安全，做了四处优化：</p>
</div><div class="cl-preview-section"><ol>
<li style="font-size: 20px; line-height: 38px;">通过自旋死循环保证一定可以新增成功。</li>
</ol>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">在新增之前，通过 <code>for (Node&lt;K,V&gt;[] tab = table;;)</code> 这样的死循环来保证新增一定可以成功，一旦新增成功，就可以退出当前死循环，新增失败的话，会重复新增的步骤，直到新增成功为止。</p>
</div><div class="cl-preview-section"><ol start="2">
<li style="font-size: 20px; line-height: 38px;">当前槽点为空时，通过 CAS 新增。</li>
</ol>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">Java 这里的写法非常严谨，没有在判断槽点为空的情况下直接赋值，因为在判断槽点为空和赋值的瞬间，很有可能槽点已经被其他线程赋值了，所以我们采用 CAS 算法，能够保证槽点为空的情况下赋值成功，如果恰好槽点已经被其他线程赋值，当前 CAS 操作失败，会再次执行 for 自旋，再走槽点有值的 put 流程，这里就是自旋 + CAS 的结合。</p>
</div><div class="cl-preview-section"><ol start="3">
<li style="font-size: 20px; line-height: 38px;">当前槽点有值，锁住当前槽点。</li>
</ol>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">put 时，如果当前槽点有值，就是 key 的 hash 冲突的情况，此时槽点上可能是链表或红黑树，我们通过锁住槽点，来保证同一时刻只会有一个线程能对槽点进行修改，截图如下：</p>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;"><img class="" src="https://img.mukewang.com/5d883acd0001833304130067.png" data-original="//img.mukewang.com/5d883acd0001833304130067.png" alt="图片描述"></p>
</div><div class="cl-preview-section"><ol start="4">
<li style="font-size: 20px; line-height: 38px;">红黑树旋转时，锁住红黑树的根节点，保证同一时刻，当前红黑树只能被一个线程旋转，代码截图如下：<br>
<img class="" src="https://img.mukewang.com/5d883adb000166bb05880443.png" data-original="//img.mukewang.com/5d883adb000166bb05880443.png" alt="图片描述"></li>
</ol>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">通过以上 4 点，保证了在各种情况下的新增（不考虑扩容的情况下），都是线程安全的，通过自旋 + CAS + 锁三大姿势，实现的很巧妙，值得我们借鉴。</p>
</div><div class="cl-preview-section"><h3 id="扩容时的线程安全">3.3 扩容时的线程安全</h3>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">ConcurrentHashMap 的扩容时机和 HashMap 相同，都是在 put 方法的最后一步检查是否需要扩容，如果需要则进行扩容，但两者扩容的过程完全不同，ConcurrentHashMap 扩容的方法叫做 transfer，从 put 方法的 addCount 方法进去，就能找到 transfer 方法，transfer 方法的主要思路是：</p>
</div><div class="cl-preview-section"><ol>
<li style="font-size: 20px; line-height: 38px;">首先需要把老数组的值全部拷贝到扩容之后的新数组上，先从数组的队尾开始拷贝；</li>
<li style="font-size: 20px; line-height: 38px;">拷贝数组的槽点时，先把原数组槽点锁住，保证原数组槽点不能操作，成功拷贝到新数组时，把原数组槽点赋值为转移节点；</li>
<li style="font-size: 20px; line-height: 38px;">这时如果有新数据正好需要 put 到此槽点时，发现槽点为转移节点，就会一直等待，所以在扩容完成之前，该槽点对应的数据是不会发生变化的；</li>
<li style="font-size: 20px; line-height: 38px;">从数组的尾部拷贝到头部，每拷贝成功一次，就把原数组中的节点设置成转移节点；</li>
<li style="font-size: 20px; line-height: 38px;">直到所有数组数据都拷贝到新数组时，直接把新数组整个赋值给数组容器，拷贝完成。</li>
</ol>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">关键源码如下：</p>
</div><div class="cl-preview-section"><pre class="  language-java"><code class="prism  language-java"><span class="token comment">// 扩容主要分 2 步，第一新建新的空数组，第二移动拷贝每个元素到新数组中去</span>
<span class="token comment">// tab：原数组，nextTab：新数组</span>
<span class="token keyword">private</span> <span class="token keyword">final</span> <span class="token keyword">void</span> <span class="token function">transfer</span><span class="token punctuation">(</span>Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span><span class="token punctuation">[</span><span class="token punctuation">]</span> tab<span class="token punctuation">,</span> Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span><span class="token punctuation">[</span><span class="token punctuation">]</span> nextTab<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token comment">// 老数组的长度</span>
    <span class="token keyword">int</span> n <span class="token operator">=</span> tab<span class="token punctuation">.</span>length<span class="token punctuation">,</span> stride<span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>stride <span class="token operator">=</span> <span class="token punctuation">(</span>NCPU <span class="token operator">&gt;</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">?</span> <span class="token punctuation">(</span>n <span class="token operator">&gt;&gt;&gt;</span> <span class="token number">3</span><span class="token punctuation">)</span> <span class="token operator">/</span> NCPU <span class="token operator">:</span> n<span class="token punctuation">)</span> <span class="token operator">&lt;</span> MIN_TRANSFER_STRIDE<span class="token punctuation">)</span>
        stride <span class="token operator">=</span> MIN_TRANSFER_STRIDE<span class="token punctuation">;</span> <span class="token comment">// subdivide range</span>
    <span class="token comment">// 如果新数组为空，初始化，大小为原数组的两倍，n &lt;&lt; 1</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>nextTab <span class="token operator">==</span> null<span class="token punctuation">)</span> <span class="token punctuation">{</span>            <span class="token comment">// initiating</span>
        <span class="token keyword">try</span> <span class="token punctuation">{</span>
            <span class="token annotation punctuation">@SuppressWarnings</span><span class="token punctuation">(</span><span class="token string">"unchecked"</span><span class="token punctuation">)</span>
            Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span><span class="token punctuation">[</span><span class="token punctuation">]</span> nt <span class="token operator">=</span> <span class="token punctuation">(</span>Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token operator">&lt;</span><span class="token operator">?</span><span class="token punctuation">,</span><span class="token operator">?</span><span class="token operator">&gt;</span><span class="token punctuation">[</span>n <span class="token operator">&lt;&lt;</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
            nextTab <span class="token operator">=</span> nt<span class="token punctuation">;</span>
        <span class="token punctuation">}</span> <span class="token keyword">catch</span> <span class="token punctuation">(</span><span class="token class-name">Throwable</span> ex<span class="token punctuation">)</span> <span class="token punctuation">{</span>      <span class="token comment">// try to cope with OOME</span>
            sizeCtl <span class="token operator">=</span> Integer<span class="token punctuation">.</span>MAX_VALUE<span class="token punctuation">;</span>
            <span class="token keyword">return</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        nextTable <span class="token operator">=</span> nextTab<span class="token punctuation">;</span>
        transferIndex <span class="token operator">=</span> n<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token comment">// 新数组的长度</span>
    <span class="token keyword">int</span> nextn <span class="token operator">=</span> nextTab<span class="token punctuation">.</span>length<span class="token punctuation">;</span>
    <span class="token comment">// 代表转移节点，如果原数组上是转移节点，说明该节点正在被扩容</span>
    ForwardingNode<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> fwd <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ForwardingNode</span><span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span><span class="token punctuation">(</span>nextTab<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">boolean</span> advance <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
    <span class="token keyword">boolean</span> finishing <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span> <span class="token comment">// to ensure sweep before committing nextTab</span>
    <span class="token comment">// 无限自旋，i 的值会从原数组的最大值开始，慢慢递减到 0</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> bound <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span><span class="token punctuation">;</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> f<span class="token punctuation">;</span> <span class="token keyword">int</span> fh<span class="token punctuation">;</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span>advance<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">int</span> nextIndex<span class="token punctuation">,</span> nextBound<span class="token punctuation">;</span>
            <span class="token comment">// 结束循环的标志</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">--</span>i <span class="token operator">&gt;=</span> bound <span class="token operator">||</span> finishing<span class="token punctuation">)</span>
                advance <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
            <span class="token comment">// 已经拷贝完成</span>
            <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>nextIndex <span class="token operator">=</span> transferIndex<span class="token punctuation">)</span> <span class="token operator">&lt;=</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                i <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
                advance <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            <span class="token comment">// 每次减少 i 的值</span>
            <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>U<span class="token punctuation">.</span><span class="token function">compareAndSwapInt</span>
                     <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">,</span> TRANSFERINDEX<span class="token punctuation">,</span> nextIndex<span class="token punctuation">,</span>
                      nextBound <span class="token operator">=</span> <span class="token punctuation">(</span>nextIndex <span class="token operator">&gt;</span> stride <span class="token operator">?</span>
                                   nextIndex <span class="token operator">-</span> stride <span class="token operator">:</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                bound <span class="token operator">=</span> nextBound<span class="token punctuation">;</span>
                i <span class="token operator">=</span> nextIndex <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span>
                advance <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        <span class="token comment">// if 任意条件满足说明拷贝结束了</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>i <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token operator">||</span> i <span class="token operator">&gt;=</span> n <span class="token operator">||</span> i <span class="token operator">+</span> n <span class="token operator">&gt;=</span> nextn<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">int</span> sc<span class="token punctuation">;</span>
            <span class="token comment">// 拷贝结束，直接赋值，因为每次拷贝完一个节点，都在原数组上放转移节点，所以拷贝完成的节点的数据一定不会再发生变化。</span>
            <span class="token comment">// 原数组发现是转移节点，是不会操作的，会一直等待转移节点消失之后在进行操作。</span>
            <span class="token comment">// 也就是说数组节点一旦被标记为转移节点，是不会再发生任何变动的，所以不会有任何线程安全的问题</span>
            <span class="token comment">// 所以此处直接赋值，没有任何问题。</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>finishing<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                nextTable <span class="token operator">=</span> null<span class="token punctuation">;</span>
                table <span class="token operator">=</span> nextTab<span class="token punctuation">;</span>
                sizeCtl <span class="token operator">=</span> <span class="token punctuation">(</span>n <span class="token operator">&lt;&lt;</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token punctuation">(</span>n <span class="token operator">&gt;&gt;&gt;</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token keyword">return</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>U<span class="token punctuation">.</span><span class="token function">compareAndSwapInt</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">,</span> SIZECTL<span class="token punctuation">,</span> sc <span class="token operator">=</span> sizeCtl<span class="token punctuation">,</span> sc <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>sc <span class="token operator">-</span> <span class="token number">2</span><span class="token punctuation">)</span> <span class="token operator">!=</span> <span class="token function">resizeStamp</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token operator">&lt;&lt;</span> RESIZE_STAMP_SHIFT<span class="token punctuation">)</span>
                    <span class="token keyword">return</span><span class="token punctuation">;</span>
                finishing <span class="token operator">=</span> advance <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
                i <span class="token operator">=</span> n<span class="token punctuation">;</span> <span class="token comment">// recheck before commit</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>f <span class="token operator">=</span> <span class="token function">tabAt</span><span class="token punctuation">(</span>tab<span class="token punctuation">,</span> i<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">==</span> null<span class="token punctuation">)</span>
            advance <span class="token operator">=</span> <span class="token function">casTabAt</span><span class="token punctuation">(</span>tab<span class="token punctuation">,</span> i<span class="token punctuation">,</span> null<span class="token punctuation">,</span> fwd<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>fh <span class="token operator">=</span> f<span class="token punctuation">.</span>hash<span class="token punctuation">)</span> <span class="token operator">==</span> MOVED<span class="token punctuation">)</span>
            advance <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span> <span class="token comment">// already processed</span>
        <span class="token keyword">else</span> <span class="token punctuation">{</span>
            <span class="token keyword">synchronized</span> <span class="token punctuation">(</span>f<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                <span class="token comment">// 进行节点的拷贝</span>
                <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">tabAt</span><span class="token punctuation">(</span>tab<span class="token punctuation">,</span> i<span class="token punctuation">)</span> <span class="token operator">==</span> f<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                    Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> ln<span class="token punctuation">,</span> hn<span class="token punctuation">;</span>
                    <span class="token keyword">if</span> <span class="token punctuation">(</span>fh <span class="token operator">&gt;=</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                        <span class="token keyword">int</span> runBit <span class="token operator">=</span> fh <span class="token operator">&amp;</span> n<span class="token punctuation">;</span>
                        Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> lastRun <span class="token operator">=</span> f<span class="token punctuation">;</span>
                        <span class="token keyword">for</span> <span class="token punctuation">(</span>Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> p <span class="token operator">=</span> f<span class="token punctuation">.</span>next<span class="token punctuation">;</span> p <span class="token operator">!=</span> null<span class="token punctuation">;</span> p <span class="token operator">=</span> p<span class="token punctuation">.</span>next<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                            <span class="token keyword">int</span> b <span class="token operator">=</span> p<span class="token punctuation">.</span>hash <span class="token operator">&amp;</span> n<span class="token punctuation">;</span>
                            <span class="token keyword">if</span> <span class="token punctuation">(</span>b <span class="token operator">!=</span> runBit<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                                runBit <span class="token operator">=</span> b<span class="token punctuation">;</span>
                                lastRun <span class="token operator">=</span> p<span class="token punctuation">;</span>
                            <span class="token punctuation">}</span>
                        <span class="token punctuation">}</span>
                        <span class="token keyword">if</span> <span class="token punctuation">(</span>runBit <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                            ln <span class="token operator">=</span> lastRun<span class="token punctuation">;</span>
                            hn <span class="token operator">=</span> null<span class="token punctuation">;</span>
                        <span class="token punctuation">}</span>
                        <span class="token keyword">else</span> <span class="token punctuation">{</span>
                            hn <span class="token operator">=</span> lastRun<span class="token punctuation">;</span>
                            ln <span class="token operator">=</span> null<span class="token punctuation">;</span>
                        <span class="token punctuation">}</span>
                        <span class="token comment">// 如果节点只有单个数据，直接拷贝，如果是链表，循环多次组成链表拷贝</span>
                        <span class="token keyword">for</span> <span class="token punctuation">(</span>Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> p <span class="token operator">=</span> f<span class="token punctuation">;</span> p <span class="token operator">!=</span> lastRun<span class="token punctuation">;</span> p <span class="token operator">=</span> p<span class="token punctuation">.</span>next<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                            <span class="token keyword">int</span> ph <span class="token operator">=</span> p<span class="token punctuation">.</span>hash<span class="token punctuation">;</span> K pk <span class="token operator">=</span> p<span class="token punctuation">.</span>key<span class="token punctuation">;</span> V pv <span class="token operator">=</span> p<span class="token punctuation">.</span>val<span class="token punctuation">;</span>
                            <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>ph <span class="token operator">&amp;</span> n<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span>
                                ln <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span><span class="token punctuation">(</span>ph<span class="token punctuation">,</span> pk<span class="token punctuation">,</span> pv<span class="token punctuation">,</span> ln<span class="token punctuation">)</span><span class="token punctuation">;</span>
                            <span class="token keyword">else</span>
                                hn <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span><span class="token punctuation">(</span>ph<span class="token punctuation">,</span> pk<span class="token punctuation">,</span> pv<span class="token punctuation">,</span> hn<span class="token punctuation">)</span><span class="token punctuation">;</span>
                        <span class="token punctuation">}</span>
                        <span class="token comment">// 在新数组位置上放置拷贝的值</span>
                        <span class="token function">setTabAt</span><span class="token punctuation">(</span>nextTab<span class="token punctuation">,</span> i<span class="token punctuation">,</span> ln<span class="token punctuation">)</span><span class="token punctuation">;</span>
                        <span class="token function">setTabAt</span><span class="token punctuation">(</span>nextTab<span class="token punctuation">,</span> i <span class="token operator">+</span> n<span class="token punctuation">,</span> hn<span class="token punctuation">)</span><span class="token punctuation">;</span>
                        <span class="token comment">// 在老数组位置上放上 ForwardingNode 节点</span>
                        <span class="token comment">// put 时，发现是 ForwardingNode 节点，就不会再动这个节点的数据了</span>
                        <span class="token function">setTabAt</span><span class="token punctuation">(</span>tab<span class="token punctuation">,</span> i<span class="token punctuation">,</span> fwd<span class="token punctuation">)</span><span class="token punctuation">;</span>
                        advance <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
                    <span class="token punctuation">}</span>
                    <span class="token comment">// 红黑树的拷贝</span>
                    <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>f <span class="token keyword">instanceof</span> <span class="token class-name">TreeBin</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                        <span class="token comment">// 红黑树的拷贝工作，同 HashMap 的内容，代码忽略</span>
                        …………
                        <span class="token comment">// 在老数组位置上放上 ForwardingNode 节点</span>
                        <span class="token function">setTabAt</span><span class="token punctuation">(</span>tab<span class="token punctuation">,</span> i<span class="token punctuation">,</span> fwd<span class="token punctuation">)</span><span class="token punctuation">;</span>
                        advance <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
                    <span class="token punctuation">}</span>
                <span class="token punctuation">}</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">扩容中的关键点，就是如何保证是线程安全的，小结有如下几点：</p>
</div><div class="cl-preview-section"><ol>
<li style="font-size: 20px; line-height: 38px;">拷贝槽点时，会把原数组的槽点锁住；</li>
<li style="font-size: 20px; line-height: 38px;">拷贝成功之后，会把原数组的槽点设置成转移节点，这样如果有数据需要 put 到该节点时，发现该槽点是转移节点，会一直等待，直到扩容成功之后，才能继续 put，可以参考 put 方法中的 helpTransfer 方法；</li>
<li style="font-size: 20px; line-height: 38px;">从尾到头进行拷贝，拷贝成功就把原数组的槽点设置成转移节点。</li>
<li style="font-size: 20px; line-height: 38px;">等扩容拷贝都完成之后，直接把新数组的值赋值给数组容器，之前等待 put 的数据才能继续 put。</li>
</ol>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">扩容方法还是很有意思的，通过在原数组上设置转移节点，put 时碰到转移节点时会等待扩容成功之后才能 put 的策略，来保证了整个扩容过程中肯定是线程安全的，因为数组的槽点一旦被设置成转移节点，在没有扩容完成之前，是无法进行操作的。</p>
</div><div class="cl-preview-section"><h2 id="get" style="font-size: 30px;">4 get</h2>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">ConcurrentHashMap 读的话，就比较简单，先获取数组的下标，然后通过判断数组下标的 key 是否和我们的 key 相等，相等的话直接返回，如果下标的槽点是链表或红黑树的话，分别调用相应的查找数据的方法，整体思路和 HashMap 很像，源码如下：</p>
</div><div class="cl-preview-section"><pre class="  language-java"><code class="prism  language-java"><span class="token keyword">public</span> V <span class="token function">get</span><span class="token punctuation">(</span>Object key<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span><span class="token punctuation">[</span><span class="token punctuation">]</span> tab<span class="token punctuation">;</span> Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> e<span class="token punctuation">,</span> p<span class="token punctuation">;</span> <span class="token keyword">int</span> n<span class="token punctuation">,</span> eh<span class="token punctuation">;</span> K ek<span class="token punctuation">;</span>
    <span class="token comment">//计算hashcode</span>
    <span class="token keyword">int</span> h <span class="token operator">=</span> <span class="token function">spread</span><span class="token punctuation">(</span>key<span class="token punctuation">.</span><span class="token function">hashCode</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment">//不是空的数组 &amp;&amp; 并且当前索引的槽点数据不是空的</span>
    <span class="token comment">//否则该key对应的值不存在，返回null</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>tab <span class="token operator">=</span> table<span class="token punctuation">)</span> <span class="token operator">!=</span> null <span class="token operator">&amp;&amp;</span> <span class="token punctuation">(</span>n <span class="token operator">=</span> tab<span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token operator">&gt;</span> <span class="token number">0</span> <span class="token operator">&amp;&amp;</span>
        <span class="token punctuation">(</span>e <span class="token operator">=</span> <span class="token function">tabAt</span><span class="token punctuation">(</span>tab<span class="token punctuation">,</span> <span class="token punctuation">(</span>n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">&amp;</span> h<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">!=</span> null<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">//槽点第一个值和key相等，直接返回</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>eh <span class="token operator">=</span> e<span class="token punctuation">.</span>hash<span class="token punctuation">)</span> <span class="token operator">==</span> h<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>ek <span class="token operator">=</span> e<span class="token punctuation">.</span>key<span class="token punctuation">)</span> <span class="token operator">==</span> key <span class="token operator">||</span> <span class="token punctuation">(</span>ek <span class="token operator">!=</span> null <span class="token operator">&amp;&amp;</span> key<span class="token punctuation">.</span><span class="token function">equals</span><span class="token punctuation">(</span>ek<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
                <span class="token keyword">return</span> e<span class="token punctuation">.</span>val<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token comment">//如果是红黑树或者转移节点，使用对应的find方法</span>
        <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>eh <span class="token operator">&lt;</span> <span class="token number">0</span><span class="token punctuation">)</span>
            <span class="token keyword">return</span> <span class="token punctuation">(</span>p <span class="token operator">=</span> e<span class="token punctuation">.</span><span class="token function">find</span><span class="token punctuation">(</span>h<span class="token punctuation">,</span> key<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">!=</span> null <span class="token operator">?</span> p<span class="token punctuation">.</span>val <span class="token operator">:</span> null<span class="token punctuation">;</span>
        <span class="token comment">//如果是链表，遍历查找</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>e <span class="token operator">=</span> e<span class="token punctuation">.</span>next<span class="token punctuation">)</span> <span class="token operator">!=</span> null<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>e<span class="token punctuation">.</span>hash <span class="token operator">==</span> h <span class="token operator">&amp;&amp;</span>
                <span class="token punctuation">(</span><span class="token punctuation">(</span>ek <span class="token operator">=</span> e<span class="token punctuation">.</span>key<span class="token punctuation">)</span> <span class="token operator">==</span> key <span class="token operator">||</span> <span class="token punctuation">(</span>ek <span class="token operator">!=</span> null <span class="token operator">&amp;&amp;</span> key<span class="token punctuation">.</span><span class="token function">equals</span><span class="token punctuation">(</span>ek<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
                <span class="token keyword">return</span> e<span class="token punctuation">.</span>val<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> null<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre>
</div><div class="cl-preview-section"><h2 id="总结" style="font-size: 30px;">5 总结</h2>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">本文摘取 ConcurrentHashMap 两个核心的方法讲解了一下，特别是 put 方法，采取了很多手段来保证了线程安全，是平时面试时的重中之重，大家可以尝试 debug 来调试一下源码，其他方法感兴趣的话，可以尝试去 GitHub 上去查看源码。</p>
</div>}
                        </div>
                    </div>
                                            <!-- 买过的阅读 -->
                        <div class="art-next-prev clearfix">
                                                                                                <!-- 已买且开放 或者可以试读 -->
                                    <a href="/read/47/article/857">
                                                                    <div class="prev l clearfix">
                                        <div class="icon l">
                                            <i class="imv2-arrow3_l"></i>
                                        </div>
                                        <p>
                                            15 CopyOnWriteArrayList 源码解析和设计思路
                                        </p>
                                    </div>
                                </a>
                                                                                                                            <!-- 已买且开放 或者可以试读 -->
                                    <a href="/read/47/article/859">
                                                                    <div class="next r clearfix">
                                        <p>
                                            17 并发 List、Map源码面试题  
                                        </p>
                                        <div class="icon r">
                                            <i class="imv2-arrow3_r"></i>
                                        </div>

                                    </div>
                                </a>
                                                    </div>
                                    </div>
                <div class="comments-con js-comments-con" id="coments_con">
                </div>

                
            </div>
            
            
            

        </div>
    </div>
</div>

<div class="modal modal-jiaQun-new hide" id="modal-jiaQun">
    <div class="inner" style="">
        <div class="modal-close js-close-jiaQun">
            <i class="imv2-close"></i>
        </div>
        <div class="content">
            <img src="https://img.mukewang.com/5d634d40000119e505400602.jpg">
            <div class="right-info">
                <div class="title">
                    扫码加入慕课Java核心用户群
                </div>
                <div class="desc">
                                            <p class="mb6">验证信息：<span id="joincode">1909271435058473</span><span class="copy js-copy-joincode">复制</span></p>
                                        <p class="mb6">QQ讨论群号：906691736</p>
                                            <p>QQ群URL：<a href="https://jq.qq.com/?_wv=1027&amp;k=55RtSbJ" target="_blank">点击访问</a></p>
                                    </div>
            </div>
            <p class="tip">若遇到搜索不到QQ群或加群失败，请联系客服邮箱:kf@imooc.com</p>
        </div>
    </div>
</div>
 
<!-- 专栏介绍页专栏评价 -->

<!-- 专栏介绍页底部三条评价 -->

<!-- 专栏阅读页弹层目录和介绍页页面目录 -->

<!-- 专栏阅读页发布回复 -->

<!-- 专栏阅读页发布评论 -->

<!-- 专栏阅读页底部评论 -->

<!-- 专栏阅读 单个 评论 -->

<!-- 新增回复和展开三条以外回复 -->

<!-- 立即订阅的弹窗 -->












</div></body></html>